package com.mid;

/**
 * Created by Lxk on 2019/6/3.
 */
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};

public class Solution138 {

    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        Node cur = head;
        Node next = null;
        while(cur!=null){
            next = cur.next;
            cur.next = new Node(cur.val,null,null);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        while(cur!=null){
            next = cur.next.next;
            cur.next.random = cur.random!=null?cur.random.next:null;
            cur = next;
        }

        boolean isFlag = false;
        cur = head;
        Node copyHead = cur.next;
        while(cur!=null){
            next = cur.next.next;
            cur.next.next = next!=null?next.next:null;
            cur.next = next;
            cur = cur.next;
        }
        return copyHead;
    }

}
